Online social network services provide users with a mechanism for defining, and memorializing in a digital format, their relationships with other people and other entities (e.g., companies, schools, etc.). This digital representation of real-world relationships is frequently referred to as a social graph and is typically implemented with a specialized database referred to as a graph database. A graph database is a particular type of database that uses graph structures with nodes, edges, and properties to represent and store data. Accordingly, when two members of a social network service establish a “connection”—for example, by mutually acknowledging their relationship—nodes representing the two members will be connected via an edge indicating the existence of the particular relationship between the two members.
As shown in FIG. 1, the node representing the member with reference number 12 has three first-degree connections (e.g., members represented by nodes 14-A, 14-B and 14-C), sometimes referred to simply as friends or direct connections. Additionally, the member represented by the node with reference number 12 has nine second-degree connections (e.g., members represented by nodes 16-A through 164), or friends-of-friends. Based on this overly simplified example, it becomes abundantly apparent that the number of people at each level increases dramatically. In real world examples, it is not uncommon for a member to have thousands, or even tens of thousands, of third-degree connections. Because of the large number of third-degree connections, it is costly and inefficient from a computing resources perspective to have an index stored in memory for the purpose of quickly identifying those members of a social network service who are third-degree connections of a particular member. Consequently, for various applications that benefit from information identifying a member's third degree connections (e.g., such as a people-search engine), there exists a need for an efficient technique by which to identify members of a social network service who are, or who are likely to be, third-degree connections of a particular member.